package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1492 {
    public long startExecuteTime = System.currentTimeMillis();

    class Solution {
        public int kthFactor(int n, int k) {
            int count = 0, factor;
            for (factor = 1; factor * factor <= n; ++factor) {
                if (n % factor == 0) {
                    ++count;
                    if (count == k) {
                        return factor;
                    }
                }
            }
            --factor;
            if (factor * factor == n) {
                --factor;
            }
            for (; factor > 0; --factor) {
                if (n % factor == 0) {
                    ++count;
                    if (count == k) {
                        return n / factor;
                    }
                }
            }
            return -1;
        }
    }

//    class Solution {
//        public int kthFactor(int n, int k) {
//            int startFactor = 2;
//            while (n > 1 && k >= 1) {
//                for (int i = startFactor; i <= n; i++) {
//                    boolean curFactor = false;
//                    while (n % i == 0) {
//                        n /= i;
//                        curFactor = true;
//                    }
//                    if (curFactor) {
//                        startFactor = i + 1;
//                        break;
//                    }
//                }
//                --k;
//            }
//
//            return startFactor;
//        }
//    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.kthFactor(12, 3));
    }

    public static void main(String[] args) throws Exception {
        LC1492 an = new LC1492();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
